//给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。 
//
// 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。 
//
// 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。 
//
// 文本的最后一行应为左对齐，且单词之间不插入额外的空格。 
//
// 说明: 
//
// 
// 单词是指由非空格字符组成的字符序列。 
// 每个单词的长度大于 0，小于等于 maxWidth。 
// 输入单词数组 words 至少包含一个单词。 
// 
//
// 示例: 
//
// 输入:
//words = ["This", "is", "an", "example", "of", "text", "justification."]
//maxWidth = 16
//输出:
//[
//   "This    is    an",
//   "example  of text",
//   "justification.  "
//]
// 
//
// 示例 2: 
//
// 输入:
//words = ["What","must","be","acknowledgment","shall","be"]
//maxWidth = 16
//输出:
//[
//  "What   must   be",
//  "acknowledgment  ",
//  "shall be        "
//]
//解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
//     因为最后一行应为左对齐，而不是左右两端对齐。       
//     第二行同样为左对齐，这是因为这行只包含一个单词。
// 
//
// 示例 3: 
//
// 输入:
//words = ["Science","is","what","we","understand","well","enough","to","explain
//",
//         "to","a","computer.","Art","is","everything","else","we","do"]
//maxWidth = 20
//输出:
//[
//  "Science  is  what we",
//  "understand      well",
//  "enough to explain to",
//  "a  computer.  Art is",
//  "everything  else  we",
//  "do                  "
//]
// 
// Related Topics 字符串 
// 👍 95 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：文本左右对齐
public class P68TextJustification {

    /**
     *
     * 思路： 以这个测试用例 "This", "is", "an", "example", "of", "text", "justification."
     *      分两步，第一步： 分割单词 一行在一组，存的是开始和结束下标，如第一行是 "This", "is", "an" ，存的是  0,2，第二行是 "example", "of", "text"，存的是 3,5
     *             第二步： 根据分割的单词，算出单词中间的间隔数，(特殊情况，一个单词算只有一个)，然后剩余的空白字符串除以间隔数，得到商和余，那么应该补充的空白数就是 商 + (该间隔是否在余数内 ? 1 : 0)
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 38 MB , 在所有 Java 提交中击败了 39.00% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> list = new ArrayList<>();

            // 分割单词 一行在一组，存的是开始和结束下标
            List<int[]> rowList = new ArrayList<>();
            int i = 0;
            while (i < words.length) {
                int[] arr = new int[2];
                arr[0] = i;
                int sum = words[i].length();
                while (i + 1 < words.length && sum <= maxWidth && sum + 1 + words[i + 1].length() <= maxWidth) {
                    sum += 1 + words[i + 1].length();
                    i++;
                }
                arr[1] = i;
                i++;
                rowList.add(arr);
            }

            // 对每一行作处理
            for (int index = 0; index < rowList.size(); index++) {
                int[] ch = rowList.get(index);
                int start = ch[0];
                int end = ch[1];
                int num = end - start + 1;  // 几个数字
                int blank = num == 1 ? 1 : num - 1;     // 空白数

                int totalStrLen = 0;    // 总字符串长度
                for (int k = start; k <= end; k++) {
                    totalStrLen += words[k].length();
                }

                int quotient = (maxWidth - totalStrLen) / blank;      // 剩余字符串长度 除以 空白数的商, 照理来说都是大于0的，因为下标之前判断的时候是算上空白的长度的
                int remainder = (maxWidth - totalStrLen) % blank;     // 剩余字符串长度 除以 空白数的余

                StringBuilder sb = new StringBuilder("");

                if (index != rowList.size() - 1) {
                    // 非最后一行
                    for (int b = 0; b < blank && start + b <= end; b++) {
                        sb.append(words[start + b]);

                        // quotient + remainder ? 1 : 0 个空白
                        int blankNum = quotient + (b < remainder ? 1 : 0);
                        for (int j = 0; j < blankNum; j++) {
                            sb.append(" ");
                        }
                    }
                    // 每行的最后一个单词要拼上，不然只会存到最后的空格
                    if (num > 1) {
                        sb.append(words[end]);
                    }
                } else {
                    // 最后一行
                    for (int w = start; w <= end; w++) {
                        sb.append(words[w]);
                        if (w != end) {
                            sb.append(" ");
                        }
                    }
                    int temp = maxWidth - sb.length();
                    for (int w = 0; w < temp; w++) {
                        sb.append(" ");
                    }
                }
                list.add(sb.toString());
            }
            return list;


        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P68TextJustification().new Solution();
//        String[] str = new String[]{};
        String[] str = new String[]{"What","must","be","acknowledgment","shall","be"};
        System.out.println(solution.fullJustify(str, 16));
        // TO TEST
    }

}